package doubleLinkedList;

// 2、无头双向链表实现

public class DoubleLinkedList {
    // ListNode 类

    // 声明头尾结点
    public ListNode head;
    public ListNode last;


    // 打印
    public void display() {
        // 循环实现 + 结点不为null就一直循环
        ListNode cur = this.head;
        while(cur != null) {
            System.out.print(cur.val+" ");

            // 注意这里缺少一个循环条件改变的条件！！！
            cur = cur.next;
        }
        System.out.println();
    }


    //得到单链表的长度：类似打印的代码
    public int size() {
        // 循环
        ListNode cur = this.head;
        int count = 0;
        while (cur != null) {
            count++;

            // 注意这里也是缺少条件变换!!!
            cur = cur.next;
        }
        return count;
    }


    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key) {
        // 循环
        ListNode cur = this.head;
        while (cur != null) {
            if(cur.val == key) {
                return true;
            }
            cur = cur.next; // 变换的条件！！
        }
        return false;
    }


    //头插法
    public void addFirst(int data) {
        // 首先创建结点
        ListNode listNode = new ListNode(data);
        // 然后判断是否为空
        ListNode cur = this.head;
        if(cur == null) {
            this.head = listNode;
            this.last = listNode;
            return ;
        }
        // 这里的cur可以直接换成head！qie最好用head！
        // 来到这里说明链表不为空
        cur.prev = listNode;
        listNode.next = cur;
        listNode.prev = null;  // 这里不要也ok：因为新创建的节点prev 和next本来就是null
        // 还有一个点不能忘记：头结点的变换！！
        this.head = listNode;
        // 尾结点是不用变换的！！头插时只有head需要往前移
    }


    //尾插法：存在错误目前！！！--已经解决！（修改后面）
    public void addLast(int data) {
        // 类似头插法
        // 首先创建结点
        ListNode listNode = new ListNode(data);
        // 然后判断是否为空
        ListNode cur = this.head;
        if(cur == null) {
            this.head = listNode;
            this.last = listNode;
            return ;
        }
        // 来到这里说明链表不为空
       /* cur.next = listNode;
        listNode.prev = cur;
        listNode.next = null;
        // 还有一个点不能忘记：尾结点的变换！！
        this.last = listNode;
        // 头结点是不用变换的！！尾插时只有last需要往后移*/

        // 修改如下：
        // 为什么一定要用last而不是cur：因为cur指向的是头结点，而尾插变换在尾结点！
        // 头插可以用cur是因为cur就是head，而头插变换在head！
        this.last.next = listNode;
        listNode.prev = this.last;
        this.last = listNode; // 一定要进行这个变换！！
    }


    // 找到index位置的节点
    public ListNode findIndex(int index) {
        ListNode cur = this.head;
        // 判断下标是否合法：
        if(index<0 || index>size()) {
            throw new IndexException(" sorry index不合法！");
        }
        while(index != 0) {
            cur = cur.next;
            index--;
        }
        return cur;
    }

    //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index,int data) {
        ListNode cur = this.head;

        // 找到index位置的节点
        ListNode indexNode = findIndex(index);
        // 创建结点：
        ListNode listNode = new ListNode(data);
        // 判断是否为空 + 是否只有一个结点
        if(cur == null) {
            this.head = listNode;
            this.last = listNode;
            return ;
        }
        // 出来就说明不是空
        // 判断是否只有一个结点：
        if(this.head == this.last) {
            // 如果插入位置是0就是头插，是size（）就是尾插
            if(index==0) {
                addFirst(data);
            }
            if(index==size()) {
                addLast(data);
            }
        } else {
            indexNode.prev.next = listNode;
            listNode.prev = indexNode.prev;
            listNode.next = indexNode;
            indexNode.prev = listNode;
        }
    }


    //删除第一次出现关键字为key的节点--出现错误：修改了循环条件中对于头尾结点的判断！！
    public void remove(int key) {
        ListNode cur = this.head;
        // 判断是否为空
        if(cur==null) {
            return ;
        }
        // 进行循环
        while(cur!=null) {
            if(cur.val==key) {
                // 判断是否为头结点 or 尾结点
                if(cur==this.head) { //头结点
                    this.head = this.head.next;
                    this.head.prev = null;
                    return;
                } else if(cur==this.last) {
                    this.last = this.last.prev;
                    this.last.next = null;
                    return;
                } else {
                    cur.prev.next = cur.next;
                    cur.next.prev = cur.prev;
                    return ;
                }
            }
            // 进行结点下移的条件！！
            cur = cur.next;
        }
    }


    //删除所有值为key的节点:对只删除一个结点进行稍微修改就行--去掉return 要让链表遍历完毕！！
    public void removeAllKey(int key) {
        ListNode cur = this.head;
        // 判断是否为空
        if(cur==null) {
            return ;
        }
        // 进行循环
        while(cur!=null) {
            if(cur.val==key) {
                // 判断是否为头结点 or 尾结点
                if(cur==this.head) { //头结点
                    this.head = this.head.next;
                    this.head.prev = null;
                } else if(cur==this.last) {
                    this.last = this.last.prev;
                    this.last.next = null;
                } else {
                    cur.prev.next = cur.next;
                    cur.next.prev = cur.prev;
                }
            }
            // 进行结点下移的条件！！！
            cur = cur.next;
        }
    }


    // 进行清空
    public void clear() {
        /*// 暴力清空：该方法不可行！！！就算头结点清空 但是依旧会有结点在引用这个地址
        this.head = null;*/

        /*// 每一个都清空：前驱后继都置null--这里的话head被修改
        ListNode cur = this.head;
        while(cur!=this.last) {
            cur = cur.next;
            this.head = null;
            this.head = cur;
        }
        this.head=null;*/

        // 进行修改如下：
        // 每一个都清空：前驱后继都置null + head/last 置null （不然会一直在引用）
        ListNode cur = this.head;
        while(cur != null) {
            ListNode curNext = cur.next;
            cur.next = null;
            cur.prev = null;
        }
        // 手动置空头尾结点
        this.head = null;
        this.last = null;
    }

}
